/*
https://leetcode.cn/problems/longest-consecutive-sequence/description/
128.最长连续序列
方钊堉 2024.10.13
并查集
*/

class UnionFind {
private:
    unordered_map<int, int> parent; // 存储每个节点的父节点
    unordered_map<int, int> rank; // 存储每个节点的秩（树的高度）

public:
    // 创建一个新的节点
    bool createNewNode(int x) {
        if (parent.count(x)) return false;
        parent[x] = x;
        rank[x] = 1;
        return true;
    }

    // 检查是否存在节点 x
    int checkNodeExist(int x) {
        if (parent.count(x) == 0) return 0;
        return 1;
    }

    // 查找函数，带路径压缩优化
    int findRoot(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]]; // 路径压缩
            x = parent[x];
        }
        return x;
    }

    // 合并两个节点所在的集合
    bool mergeNodes(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if (rootP == rootQ) return false;
        if (rank[rootP] < rank[rootQ]) {
            parent[rootP] = rootQ;
            rank[rootQ] += rank[rootP];
        } else {
            parent[rootQ] = rootP;
            rank[rootP] += rank[rootQ];
        }
        return true;
    }

    // 检查两个节点是否连接
    bool isConnected(int p, int q) {
        return findRoot(p) == findRoot(q);
    }

    // 返回连通分量的数量
    int getComponentCount() {
        int res = 0;
        for (const auto &[key, val] : parent) {
            if (key == val) res++;
        }
        return res;
    }

    // 将所有节点的父节点更新为其根节点
    void updateAllRoots() {
        for (auto &[key, val] : parent) {
            parent[key] = findRoot(key);
        }
    }

    // 返回最大连通分量的大小
    int getMaxGroupSize() {
        unordered_map<int, int> groupSize;
        updateAllRoots();
        int res = 0;
        for (const auto &[key, val] : parent) {
            groupSize[val]++;
            res = max(res, groupSize[val]);
        }
        return res;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        UnionFind uf;
        for (int num : nums) {
            if (uf.checkNodeExist(num) == 0) uf.createNewNode(num);
            if (uf.checkNodeExist(num - 1)) {
                uf.mergeNodes(num - 1, num);
            }
            if (uf.checkNodeExist(num + 1)) {
                uf.mergeNodes(num + 1, num);
            }
        }
        return uf.getMaxGroupSize();
    }
};